package com.lw.leetcode.back.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 473. 火柴拼正方形
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/27 16:30
 */
public class Makesquare {

    public static void main(String[] args) {
        Makesquare test = new Makesquare();
        // true
        int[] arr = {1, 1, 2, 2, 2};

        // false
//        int[] arr = {3,3,3,3,4};

        // true
//        int[] arr = {30, 30, 40, 25, 50, 12, 13, 36, 25, 14, 25, 48, 2, 36, 14};

        // false
//        int[] arr = {30, 30, 40, 25, 50, 12, 13, 36, 25, 14, 25, 48, 2, 36, 18};

        // false
//        int[] arr = {5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3};

        // false
//        int[] arr = {5, 5, 5, 5, 16, 4, 4, 4, 4, 4, 3, 3, 3, 3, 4};

        // false
//        int[] arr = {3, 9, 2, 2, 2, 9, 10, 8, 3, 9, 10, 10, 1, 9, 9};

        long l = System.currentTimeMillis();
        boolean makesquare = test.makesquare(arr);
        System.out.println(System.currentTimeMillis() - l);
        System.out.println(makesquare);


    }

    private int[] matchsticks;
    private long t;
    private int count;

    public boolean makesquare(int[] matchsticks) {
        Arrays.sort(matchsticks);
        this.matchsticks = matchsticks;
        long sum = 0;
        for (long matchstick : matchsticks) {
            sum += matchstick;
        }
        if ((sum & 3) != 0) {
            return false;
        }
        t = sum >> 2;

        int matchstick = matchsticks[matchsticks.length - 1];
        matchsticks[matchsticks.length - 1] = 0;
        return find(matchstick);
    }

    private boolean find(long sum) {
        if (sum == t) {
            count++;
            return find(0);
        }
        if (count == 3) {
            return true;
        }
        long item = -1L;
        for (int i = matchsticks.length - 1; i >= 0; i--) {
            long matchstick = matchsticks[i];
            if (matchstick == 0 || matchstick == item) {
                continue;
            }
            item = matchstick;
            matchsticks[i] = 0;
            if (sum + matchstick < t) {
                if (find(sum + matchstick)) {
                    return true;
                }
            } else if (sum + matchstick == t) {
                count++;
                if (find(0)) {
                    return true;
                }
                count--;
            }
            matchsticks[i] = (int) matchstick;
        }
        return false;
    }

}
